package demo4;

import java.util.*;

public class Solution {

    public String modifyString(String s) {
        char[] ch = s.toCharArray();

        for(int i = 0; i < ch.length; i++){
            if(ch[i] == '?'){
                for(char x = 'a'; x <= 'z'; x++){
                    if((i == 0 || ch[i - 1] != x) && (i == ch.length - 1 || ch[i + 1] != x)){
                        ch[i] = x;
                        break;
                    }
                }
            }
        }
        return String.valueOf(ch);
    }

    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ret = 0;
        for(int i = 1; i < timeSeries.length; i++){
            int len = timeSeries[i] - timeSeries[i - 1];
            if(len >= duration){
                ret += duration;
            }else{
                ret += len;
            }
        }
        return ret + duration;
    }

    public String convert(String s, int numRows) {
        if(numRows == 1) { return s;}
        int n =s.length(), d = 2 * numRows - 2;
        char[] ch = s.toCharArray();
        StringBuffer buf = new StringBuffer();

        for(int i = 0; i < n; i+=d){buf.append(ch[i]);}
        for(int i = 1; i < numRows - 1; i++){
            for(int x = i, y = d - i; x < n || y < n; x += d, y += d){
                if(x < n) { buf.append(ch[x]);}
                if(y < n) { buf.append(ch[y]);}
            }
        }
        for(int i = numRows - 1; i < n; i+=d) { buf.append(ch[i]);}
        return buf.toString();
    }

    public String countAndSay(int n) {
        String ret = "1";
        for (int i = 2; i <= n; i++) {
            StringBuffer buf = new StringBuffer();
            for (int left = 0, right = 0; right < ret.length(); ) {
                while (right < ret.length() && ret.charAt(right) == ret.charAt(left)) {
                    right++;
                }
                buf.append(Integer.toString(right - left));
                buf.append(ret.charAt(left));
                left = right;
            }
            ret = buf.toString();
        }
        return ret;
    }

    public void sortColors(int[] nums) {
        int left = -1, right = nums.length, i = 0;
        while(i < right){
            if(nums[i] == 0){
                swap(nums, ++left, i++);
            }else if(nums[i] == 2){
                swap(nums, --right, i);
            }else{
                i++;
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
}
